Step 4: pop() - The "Swap and Pop" Trick

This is the most complex operation. We can't just remove heap[0]!

The pop() Algorithm

  1. Save the root (the max value) to return later.
  2. Use self.heap.pop() to remove the *last* element.
  3. Move that last_val to the root.
  4. The heap is now broken at the root.
  5. Call self.bubble_down(0) to fix it.
  6. Return the max_val you saved.

Guidance for Step 4

  • Your blanks correspond to the root index (0). You need to save the value from the root, move the new value to the root, and start bubbling down from the root. 
# ... (inside PriorityQueue class) ...

    def pop(self):
        """
        Removes and returns the maximum key.
        Returns "null" if the heap is empty.
        """
        if self.is_empty():
            return "null"

        # 1. Get the value of the last element
        last_val = self.heap.pop()
        
        # 2. If the heap is now empty, 'last_val' was the only element
        if self.is_empty():
            return last_val
            
        # 3. Otherwise, save the max value (the root) to return later
        max_val = self.heap[____]
        
        # 4. Move the last element to the root
        self.heap[____] = last_val
        
        # 5. Start the recursive bubble down from the root
        self.bubble_down(____)

        return max_val
Copied!